#include <bits/stdc++.h>

using namespace std;

//超时了？？
class Solution1 {
    int lens,lenp;
    
    bool helper(string s,int si,string p,int pi){
        //边界返回
        if(si==lens&&pi==lenp) return true;
        if(si>lens||pi>lenp) return false;

        if((s[si]==p[pi]||p[pi]=='.')&&p[pi+1]!='*'){
            return helper(s,si+1,p,pi+1);
        }else if((s[si]==p[pi]||p[pi]=='.')&&p[pi+1]=='*'){
            return helper(s,si+1,p,pi)||helper(s,si,p,pi+2);
        }
        
        if(p[pi+1]=='*'){
            return helper(s,si,p,pi+2);
        }
        return false;
    }
public:
    bool isMatch(string s, string p) {
        lens=s.size();
        lenp=p.size();
        return helper(s,0,p,0);
    }
};
//又超时了
class Solution2 {
    int lens,lenp;
    
    bool helper(string s,int si,string p,int pi){
        //边界返回
        if(si==lens&&pi==lenp) return true;

        if(pi!=lenp && p[pi+1]=='*'){
            if(helper(s,si,p,pi+2)) return true;
        }

        if(s[si]==p[pi]||(p[pi]=='.'&&si!=lens)){
            if (helper(s,si+1,p,pi+1)) return true;
            if(p[pi+1]=='*'&& helper(s,si+1,p,pi)) return true;
        }
        
        return false;
    }
public:
    bool isMatch(string s, string p) {
        lens=s.size();
        lenp=p.size();
        return helper(s,0,p,0);
    }
};
//过了，但是时间复杂度还是有点高
class Solution3 {
    bool helper(string s,string p){
        if(s.length()==0){
            if(p.length()&1)return false;
            int i=1;
            while(i<p.length()){
                if(p[i]!='*') return false;
                i+=2;
            }
            return true;
        }
        if(p.length()==0) return false;

        if(p.length()>=2&&p[1]=='*'){
            if(helper(s,p.substr(2))){
                return true;
            }   
        }
        if(p[0]=='.'||s[0]==p[0]){
            if(helper(s.substr(1),p.substr(1))) return true;
            if(p.length()>=2&&p[1]=='*'&&helper(s.substr(1),p)) return true;
        }
        return false;
    }
public:
    bool isMatch(string s, string p) {
        return helper(s,p);
    }
};
//考虑将它改为dp
class Solution {
public:
    bool isMatch(string s, string p) {
        int m=s.length(),n=p.length();
        bool dp[m+1][n+1];
        memset(dp,0,sizeof(dp));
        dp[0][0]=true;
        for(int i=0;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(p[j-1]=='*'){
                    if(j>=2){
                        dp[i][j]= (dp[i][j]||dp[i][j-2]);
                    }
                    if(i>=1&&j>=2&&(s[i-1]==p[j-2]||p[j-2]=='.')){
                        dp[i][j]= (dp[i][j]||dp[i-1][j]);
                    }
                }else if(i>=1&&(s[i-1]==p[j-1]||p[j-1]=='.')){
                    dp[i][j]= dp[i-1][j-1];
                }   
            }
        }
        return dp[m][n];
    }
};

int main(){
    freopen("in.txt","r",stdin);
    Solution s;
    string s1,s2;
    while(cin >> s1>>s2){
        cout << s1 << " " << s2 << " ";
        int start=clock();
        cout << (s.isMatch(s1,s2)?"true":"false")<<" ";
        int end=clock();
        cout << "用时: "<< ((double)(end-start)/CLOCKS_PER_SEC)*1000 << " ms"<<endl;
    }    



    return 0;
}